package tree.binary_tree.base;

import java.util.List;

/**
 * 二叉查找树的新增、查找、删除、排序
 * 二叉查找树是最常用的一种二叉树，它支持快速插入、删除、查找操作，
 * 各个操作的时间复杂度跟树的高度成正比，理想情况下（平衡二叉查找树），时间复杂度是 O(logn)。
 * 退化成链表则为O(n)
 *
 * @author yeyangtao created at 11:17 2020/10/10
 */
public interface BinarySearchTree {

    void insert(int value);

    MyTree<?> search(int target);

    /**
     * 第一种情况是，如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为 null。
     * <p>
     * 第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），
     * 我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。
     * <p>
     * 第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。
     * 我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。
     * 然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），
     * 所以，我们可以应用上面两条规则来删除这个最小节点。
     */
    void delete(int value);

    /**
     * 中序遍历二叉查找树即为从小到大排序
     */
    List<Integer> sort();
}
